package week_seven;

public class SurroundedRegionsDisJointSets_130 {

    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private int m, n;
    int[] fa;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        fa = new int[m * n + 1];
        for (int i = 0; i < m * n + 1; i++) fa[i] = i;
        // for(int i=0;i<m*n+1;i++) System.out.println(fa[i]);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    for (int k = 0; k < 4; k++) {
                        int nextx = i + dx[k];
                        int nexty = j + dy[k];
                        if (nextx < 0 || nextx > m - 1 || nexty < 0 || nexty > n - 1)
                            union(getIndex(i, j), m * n);
                        else if (board[nextx][nexty] == 'O') {
                            union(getIndex(nextx, nexty), getIndex(i, j));
                        }
                    }
                }
            }
        }

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                // System.out.println(i+" "+j+" "+find(getIndex(i, j)));
                if (board[i][j] == 'O' && find(getIndex(i, j)) != find(m * n))
                    board[i][j] = 'X';
            }
    }

    int getIndex(int i, int j) {
        return i * n + j;
    }

    private void union(int x, int y) {
        x = find(x);
        y = find(y);
        // System.out.println("Union "+x +" to " +y);
        if (x != y) {
            // System.out.println("Union "+x +" to " +y);
            fa[x] = y;
        }
    }

    private int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
}